package br.edu.unifei.mestrado.kl.util;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Random;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import br.edu.unifei.mestrado.commons.graph.GraphProperties;
import br.edu.unifei.mestrado.commons.graph.NodeWrapper;
import br.edu.unifei.mestrado.commons.graph.RelationshipWrapper;
import br.edu.unifei.mestrado.commons.partition.AbstractPartition;
import br.edu.unifei.mestrado.commons.partition.AbstractPartitionIndex;

public class Partition extends AbstractPartition {
	private Logger logger = LoggerFactory.getLogger(this.getClass());

	private static int TWO_WAY = 2;
	/*
	 * Estrutura de dados PARTITION.
	 */
	private AbstractPartitionIndex index = null;

	public Partition(int level, AbstractPartitionIndex index) {
		super(level, TWO_WAY, index);
		this.index = index;
	}

	private interface PartitionChooser {
		public int getNextPartition(NodeWrapper node);
	}

	private class FixedChooser implements PartitionChooser {
		
		public FixedChooser() {
			logger.info("Gerando nova particao fixa.");
		}

		@Override
		public int getNextPartition(NodeWrapper node) {
			Long id = node.getId();
			return (int) (id % 2) + 1;
		}
	}

	private class ArbitraryChooser implements PartitionChooser {

		private Random rand;

		public ArbitraryChooser(Random rand) {
			this.rand = rand;
			logger.info("Gerando nova particao aleatoria.");
		}

		@Override
		public int getNextPartition(NodeWrapper node) {
			return Math.abs(rand.nextInt() % 2) + 1;
		}
	}

	public void initialFixedPartition(Iterable<NodeWrapper> allNodes) {
		initialPartition(allNodes, new FixedChooser());
	}

	public void initialArbitraryPartition(int it, Iterable<NodeWrapper> allNodes) {
		// TODO: Verificar: sempre está pegando os mesmos nós
		// initialPartition(allNodes, new ArbitraryChooser(new Random((long) (it * Math.PI))));
		// TODO: verificar a melhor semente pra colocar aqui.
		initialPartition(allNodes, new ArbitraryChooser(new Random(System.currentTimeMillis())));
	}

	/**
	 * Divide os vertices, tal que cada parte contém aproximadamente metade dos pesos dos vértices do grafo
	 */
	private void initialPartition(Iterable<NodeWrapper> allNodes, PartitionChooser chooser) {

		// UTIL: variaveis para balancear o particionamento baseado nos pesos dos nós
		int weightSet1 = 0;
		int weightSet2 = 0;

		for (NodeWrapper node : allNodes) {
			if (node.hasProperty(GraphProperties.ID)) {
				int partition = -1;
				int weight = node.getWeight();
				if (weightSet1 + weight > weightSet2) {
					partition = PART_2;
				} else if (weightSet2 + weight > weightSet1) {
					partition = PART_1;
				} else {
					partition = chooser.getNextPartition(node);
				}
				if (partition == PART_1) {
					weightSet1 += weight;
				} else {
					weightSet2 += weight;
				}
				node.setPartition(partition);
				index.insertToIndex(node, GraphProperties.PARTITION, partition);
			} else {
				// TODO: verificar pq o node zero nao tem name
				logger.debug("NodeWrapper " + node + " has no property " + GraphProperties.ID);
			}
		}
	}

	public void generateBoundaryPartition(Iterable<RelationshipWrapper> allRelationships) {
		for (RelationshipWrapper rel : allRelationships) {
			if (rel.isRelationshipOnCut()) {
				NodeWrapper startNode = rel.getStartNode();
				NodeWrapper endNode = rel.getEndNode();
				// inclui somente os vertices que estiverem no corte
				index.insertToIndex(startNode, GraphProperties.PARTITION, startNode.getPartition(), rel);
				index.insertToIndex(endNode, GraphProperties.PARTITION, endNode.getPartition(), rel);
			}
		}
	}

	/*
	 * Troca os pares na partição inicial.
	 */
	public void exchangePairs(List<PairGain> list, int qtd) {
		for (int i = 0; i < qtd; i++) {
			PairGain pair = list.get(i);

			logger.debug("Exchanging {} with {} gain: {}", new Object[] { pair.getI(), pair.getJ(),
					pair.getGain() });

			int pI = pair.getI().getPartition();
			int pJ = pair.getJ().getPartition();

			pair.getI().setPartition(pJ);
			index.updateIndex(pair.getI(), GraphProperties.PARTITION, pI, pJ);

			pair.getJ().setPartition(pI);
			index.updateIndex(pair.getJ(), GraphProperties.PARTITION, pJ, pI);
		}
	}

	/**
	 * Retorna o iterable correspondente as duas partições.
	 * 
	 * @return
	 */
	public Iterable<NodeWrapper> getAllNodes() {

		return new Iterable<NodeWrapper>() {
			@Override
			public Iterator<NodeWrapper> iterator() {
				return new Iterator<NodeWrapper>() {

					final Iterator<NodeWrapper> part1 = index.queryNodes(GraphProperties.PARTITION, PART_1)
							.iterator();
					final Iterator<NodeWrapper> part2 = index.queryNodes(GraphProperties.PARTITION, PART_2)
							.iterator();

					@Override
					public NodeWrapper next() {
						if (part1.hasNext()) {
							return part1.next();
						}
						return part2.next();
					}

					@Override
					public boolean hasNext() {
						if (part1.hasNext()) {
							return true;
						}
						return part2.hasNext();
					}

					@Override
					public void remove() {
					}
				};
			}
		};
	}

	/**
	 * Inclui os nós visinhos a baseNode que ainda não estão em nenhuma partição. <br>
	 * E inclui os vizinhos de I e J na partição de I e J respectivamente <br>
	 * 
	 * Usado somente pelo BKL.
	 * 
	 * @param baseNode
	 * @return
	 */
	public List<NodeWrapper> includeNodesToFrontier(NodeWrapper baseNode) {
		final List<NodeWrapper> justIncluded = new ArrayList<NodeWrapper>();
		// UTIL: inclui os vértices adjacentes a baseNode, pq eles se tornaram fronteira
		for (RelationshipWrapper aresta : baseNode.getRelationships()) {
			NodeWrapper other = aresta.getOtherNode(baseNode);
			if (!other.isLocked()) { // se a outra ponta nao foi usada
				long idVertice = other.getId();
				if (!index.containsKey(idVertice)) {
					justIncluded.add(other);

					// UTIL: já adiciona o vertice na partição correta.
					index.insertToIndex(other, GraphProperties.PARTITION, baseNode.getPartition(), aresta);
				}
			}
		}
		if (justIncluded.size() > 0) {
			logger.info("Novos vertices na fronteira (" + justIncluded.size() + "): ");
			logger.debug(": {}", new Object() {
				@Override
				public String toString() {
					StringBuffer b = new StringBuffer();
					for (NodeWrapper node : justIncluded) {
						b.append(node.getId() + ", ");
					}
					return b.toString();
				}
			});
		}
		return justIncluded;
	}

	public void printPartitions() {
		printSets();
	}

}
